package club.xiaojiawei.binarytree;

import java.util.LinkedList;

/**
 * @author 肖嘉威
 * @version 1.0
 * @date 5/15/22 2:11 PM
 * @question 404. 左叶子之和
 * @description 给定二叉树的根节点 root ，返回所有左叶子之和。
 */
public class SumOfLeftLeaves404 {

    public static void main(String[] args) {
        TreeNode root = new TreeNode(3);
        root.left = new TreeNode(9);
        TreeNode right = new TreeNode(20);
        right.left = new TreeNode(15);
        right.right = new TreeNode(7);
        root.right = right;
        int result = sumOfLeftLeaves2(root);
        System.out.println("值为："+result);
    }

    /**
     * DFS+递归
     * @param root
     * @return
     */
    public static int sumOfLeftLeaves(TreeNode root) {
        return recursion(root, false);
    }

    public static int recursion(TreeNode node, boolean direction){
        if (node == null){
            return 0;
        }else if (node.right == null && node.left == null){
            if (direction){
                return node.val;
            }
            return 0;
        }
        return recursion(node.left, true) + recursion(node.right, false);
    }

    /**
     * BFS+队列
     * @param root
     * @return
     */
    public static int sumOfLeftLeaves2(TreeNode root) {
        LinkedList<TreeNode> queue = new LinkedList<>();
        queue.add(root);
        int count = 0;
        while (queue.size() > 0){
            TreeNode current = queue.pop();
            if (current.left != null){
                if (current.left.right == null && current.left.left == null){
                    count += current.left.val;
                }
                queue.add(current.left);
            }
            if (current.right != null){
                queue.add(current.right);
            }
        }
        return count;
    }

    static class TreeNode{

        private int val;

        private TreeNode left;

        private TreeNode right;

        public TreeNode(int val) {
            this.val = val;
        }

        public int getVal() {
            return val;
        }

        public void setVal(int val) {
            this.val = val;
        }

        public TreeNode getLeft() {
            return left;
        }

        public void setLeft(TreeNode left) {
            this.left = left;
        }

        public TreeNode getRight() {
            return right;
        }

        public void setRight(TreeNode right) {
            this.right = right;
        }
    }
}
